题目链接 · 灵神原题解（署名来源）

方法一：最小堆

合并后的第一个节点 $\mathit{\text{first}}$，一定是某个链表的头节点（因为链表已按升序排列）。

合并后的第二个节点，可能是某个链表的头节点，也可能是 $\mathit{\text{first}}$ 的下一个节点。

例如有三个链表 1->2->5, 3->4->6, 4->5->6，找到第一个节点 1 之后，第二个节点不是另一个链表的头节点，而是节点 1 的下一个节点 2。

按照这个过程继续思考，每当我们找到一个节点值最小的节点 $x$，就把节点 $x.\mathit{\text{next}}$ 加入「可能是最小节点」的集合中。

因此，我们需要一个数据结构，它支持：

• 从数据结构中找到并移除最小节点。
• 插入节点。

这可以用最小堆实现。初始把所有链表的头节点入堆，然后不断弹出堆中最小节点 $x$，如果 $x.\mathit{\text{next}}$ 不为空就加入堆中。循环直到堆为空。把弹出的节点按顺序拼接起来，就得到了答案。

实现时，可以用哨兵节点简化代码，具体请看【基础算法精讲 06】。

Python 解法1

# 让堆可以比较节点大小（不改 __lt__ 的写法见 Python3 写法二）
ListNode.__lt__ = lambda a, b: a.val < b.val  

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 哨兵节点，作为合并后链表头节点的前一个节点
        h = [head for head in lists if head]  # 把所有非空链表的头节点入堆
        heapify(h)  # 堆化
        while h:  # 循环直到堆为空
            node = heappop(h)  # 剩余节点中的最小节点
            if node.next:  # 下一个节点不为空
                heappush(h, node.next)  # 下一个节点有可能是最小节点，入堆
            cur.next = node  # 把 node 添加到新链表的末尾
            cur = cur.next  # 准备合并下一个节点
        return dummy.next  # 哨兵节点的下一个节点就是新链表的头节点

C++ 解法1

// C++ 版待补充

Python 解法2

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 哨兵节点，作为合并后链表头节点的前一个节点
        # 额外保存 i，这样即使 val 相同也不会去比 ListNode，避免报错）
        h = [(head.val, i, head) for i, head in enumerate(lists) if head]  # 把所有非空链表的头节点入堆
        heapify(h)  # 堆化
        while h:  # 循环直到堆为空
            _, i, node = heappop(h)  # 剩余节点中的最小节点
            if node.next:  # 下一个节点不为空
                heappush(h, (node.next.val, i, node.next))  # 下一个节点有可能是最小节点，入堆
            cur.next = node  # 把 node 添加到新链表的末尾
            cur = cur.next  # 准备合并下一个节点
        return dummy.next  # 哨兵节点的下一个节点就是新链表的头节点

C++ 解法2

// C++ 版待补充

C++ 解法3

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](const ListNode* a, const ListNode* b) {
            return a->val > b->val; // 最小堆
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;
        for (auto head : lists) {
            if (head) {
                pq.push(head); // 把所有非空链表的头节点入堆
            }
        }

        ListNode dummy{}; // 哨兵节点，作为合并后链表头节点的前一个节点
        auto cur = &dummy;
        while (!pq.empty()) { // 循环直到堆为空
            auto node = pq.top(); // 剩余节点中的最小节点
            pq.pop();
            if (node->next) { // 下一个节点不为空
                pq.push(node->next); // 下一个节点有可能是最小节点，入堆
            }
            cur->next = node; // 把 node 添加到新链表的末尾
            cur = cur->next; // 准备合并下一个节点
        }
        return dummy.next; // 哨兵节点的下一个节点就是新链表的头节点
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(L\log m)$，其中 $m$ 为 $\mathit{\text{lists}}$ 的长度，$L$ 为所有链表的长度之和。
• 空间复杂度：$\mathcal{O}(m)$。堆中至多有 $m$ 个元素。

方法二：分治

暴力做法是，按照 21. 合并两个有序链表 的 题解思路，先合并前两个链表，再把得到的新链表和第三个链表合并，再和第四个链表合并，依此类推。

但是这种做法，平均每个节点会参与到 $\mathcal{O}(m)$ 次合并中（用 $(1+2+\cdots +m)/m$ 粗略估计），所以总的时间复杂度为 $\mathcal{O}(L\cdot m)$。

一个巧妙的思路是，把 $\mathit{\text{lists}}$ 一分为二（尽量均分），先合并前一半的链表，再合并后一半的链表，然后把这两个链表合并成最终的链表。如何合并前一半的链表呢？我们可以继续一分为二。如此分下去直到只有一个链表，此时无需合并。

我们可以写一个递归来完成上述逻辑，如果你对递归头晕，请看【基础算法精讲 09】。

按照一分为二再合并的逻辑，递归像是在后序遍历一棵平衡二叉树。由于平衡树的高度是 $\mathcal{O}(\log m)$，所以每个链表节点只会出现在 $\mathcal{O}(\log m)$ 次合并中！这样就做到了更快的 $\mathcal{O}(L\log m)$ 时间。

写法一：递归

Python 解法4

class Solution:
    # 21. 合并两个有序链表
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1  # 把 list1 加到新链表中
                list1 = list1.next
            else:  # 注：相等的情况加哪个节点都是可以的
                cur.next = list2  # 把 list2 加到新链表中
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2  # 拼接剩余链表
        return dummy.next

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        m = len(lists)
        if m == 0:
            return None
        if m == 1:
            return lists[0]  # 无需合并，直接返回
        left = self.mergeKLists(lists[:m // 2])  # 合并左半部分
        right = self.mergeKLists(lists[m // 2:])  # 合并右半部分
        return self.mergeTwoLists(left, right)  # 最后把左半和右半合并

C++ 解法4

// C++ 版待补充

C++ 解法5

class Solution {
    // 21. 合并两个有序链表
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy{}; // 用哨兵节点简化代码逻辑
        auto cur = &dummy; // cur 指向新链表的末尾
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1; // 把 list1 加到新链表中
                list1 = list1->next;
            } else { // 注：相等的情况加哪个节点都是可以的
                cur->next = list2; // 把 list2 加到新链表中
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2; // 拼接剩余链表
        return dummy.next;
    }

    // 合并从 lists[i] 到 lists[j-1] 的链表
    ListNode* mergeKLists(vector<ListNode*>& lists, int i, int j) {
        int m = j - i;
        if (m == 0) {
            return nullptr; // 注意输入的 lists 可能是空的
        }
        if (m == 1) {
            return lists[i]; // 无需合并，直接返回
        }
        auto left = mergeKLists(lists, i, i + m / 2); // 合并左半部分
        auto right = mergeKLists(lists, i + m / 2, j); // 合并右半部分
        return mergeTwoLists(left, right); // 最后把左半和右半合并
    }

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergeKLists(lists, 0, lists.size());
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(L\log m)$，其中 $m$ 为 $\mathit{\text{lists}}$ 的长度，$L$ 为所有链表的长度之和。每个节点参与链表合并的次数为 $\mathcal{O}(\log m)$ 次，一共有 $L$ 个节点，所以总的时间复杂度为 $\mathcal{O}(L\log m)$。
• 空间复杂度：$\mathcal{O}(\log m)$。递归深度为 $\mathcal{O}(\log m)$，需要 $\mathcal{O}(\log m)$ 的栈空间。Python 忽略切片产生的额外空间。

写法二：迭代

直接自底向上合并链表：

• 两两合并：把 $\mathit{\text{lists}}[0]$ 和 $\mathit{\text{lists}}[1]$ 合并，合并后的链表保存在 $\mathit{\text{lists}}[0]$ 中；把 $\mathit{\text{lists}}[2]$ 和 $\mathit{\text{lists}}[3]$ 合并，合并后的链表保存在 $\mathit{\text{lists}}[2]$ 中；依此类推。
• 四四合并：把 $\mathit{\text{lists}}[0]$ 和 $\mathit{\text{lists}}[2]$ 合并（相当于合并前四条链表），合并后的链表保存在 $\mathit{\text{lists}}[0]$ 中；把 $\mathit{\text{lists}}[4]$ 和 $\mathit{\text{lists}}[6]$ 合并，合并后的链表保存在 $\mathit{\text{lists}}[4]$ 中；依此类推。
• 八八合并：把 $\mathit{\text{lists}}[0]$ 和 $\mathit{\text{lists}}[4]$ 合并（相当于合并前八条链表），合并后的链表保存在 $\mathit{\text{lists}}[0]$ 中；把 $\mathit{\text{lists}}[8]$ 和 $\mathit{\text{lists}}[12]$ 合并，合并后的链表保存在 $\mathit{\text{lists}}[8]$ 中；依此类推。
• 依此类推，直到所有链表都合并到 $\mathit{\text{lists}}[0]$ 中。最后返回 $\mathit{\text{lists}}[0]$。

Python 解法6

class Solution:
    # 21. 合并两个有序链表
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1  # 把 list1 加到新链表中
                list1 = list1.next
            else:  # 注：相等的情况加哪个节点都是可以的
                cur.next = list2  # 把 list2 加到新链表中
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2  # 拼接剩余链表
        return dummy.next

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        m = len(lists)
        if m == 0:
            return None
        step = 1
        while step < m:
            for i in range(0, m - step, step * 2):
                lists[i] = self.mergeTwoLists(lists[i], lists[i + step])
            step *= 2
        return lists[0]

C++ 解法6

// C++ 版待补充

C++ 解法7

class Solution {
    // 21. 合并两个有序链表
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy{}; // 用哨兵节点简化代码逻辑
        auto cur = &dummy; // cur 指向新链表的末尾
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1; // 把 list1 加到新链表中
                list1 = list1->next;
            } else { // 注：相等的情况加哪个节点都是可以的
                cur->next = list2; // 把 list2 加到新链表中
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2; // 拼接剩余链表
        return dummy.next;
    }

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int m = lists.size();
        if (m == 0) {
            return nullptr;
        }
        for (int step = 1; step < m; step *= 2) {
            for (int i = 0; i < m - step; i += step * 2) {
                lists[i] = mergeTwoLists(lists[i], lists[i + step]);
            }
        }
        return lists[0];
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(L\log m)$，其中 $m$ 为 $\mathit{\text{lists}}$ 的长度，$L$ 为所有链表的长度之和。外层关于 $\mathit{\text{step}}$ 的循环是 $\mathcal{O}(\log m)$ 次，内层相当于把每个链表节点都遍历了一遍，是 $\mathcal{O}(L)$ 的，所以总的时间复杂度为 $\mathcal{O}(L\log m)$。
• 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府